SIAM Journal on Computing -- 1999

By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

© SIAM

SIAM Journal on Computing

Table of Contents

Available Volumes| Issue Index| View myArticles

Search This Issue

Volume 29, Issue 1, pp. 1-350

Please Note: Electronic articles are available well in advance of the printed articles.

Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions

Uriel Feige, Dror Lapidot, and Adi Shamir

pp. 1-28

BibTeX Abstract Full Text: PDF

Tight Analyses of Two Local Load Balancing Algorithms

Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, Andréa W. Richa, Robert E. Tarjan, and David Zuckerman

pp. 29-64

BibTeX Abstract Full Text: PDF

An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications

Xin He and Zhi-Zhong Chen

pp. 65-80

BibTeX Abstract Full Text: PDF

Regular Closure of Deterministic Languages

Eberhard Bertsch and Mark-Jan Nederhof

pp. 81-102

BibTeX Abstract Full Text: PDF

Constructing Evolutionary Trees in the Presence of Polymorphic Characters

Maria Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph

pp. 103-131

BibTeX Abstract Full Text: PDF

The Complexity of Tree Automata and Logics of Programs

E. Allen Emerson and Charanjit S. Jutla

pp. 132-158

BibTeX Abstract Full Text: PDF

Finding Separator Cuts in Planar Graphs within Twice the Optimal

Naveen Garg, Huzur Saran, and Vijay V. Vazirani

pp. 159-179

BibTeX Abstract Full Text: PDF

Balanced Allocations

Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal

pp. 180-200

BibTeX Abstract Full Text: PDF

The Algorithmic Aspects of Uncrowded Hypergraphs

Claudia Bertram-Kretzberg and Hanno Lefmann

pp. 201-230

BibTeX Abstract Full Text: PDF

Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs

Jerzy Marcinkowski

pp. 231-257

BibTeX Abstract Full Text: PDF

Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults

Tom Leighton and Yuan Ma

pp. 258-273

BibTeX Abstract Full Text: PDF

Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete

Tibor Szkaliczki

pp. 274-287

BibTeX Abstract Full Text: PDF

On Regular Tree Embeddings

Weimin Chen and Volker Turau

pp. 288-301

BibTeX Abstract Full Text: PDF

Equivalence of Measures of Complexity Classes

Josef M. Breutzmann and Jack H. Lutz

pp. 302-326

BibTeX Abstract Full Text: PDF

The Swapping Problem on a Line

Shoshana Anily, Michel Gendreau, and Gilbert Laporte

pp. 327-335

BibTeX Abstract Full Text: PDF

How Good is the Goemans--Williamson MAX CUT Algorithm?

pp. 336-350

BibTeX Abstract Full Text: PDF